package n_10;

/**
 * @author ChengMiao
 * @title: Demo
 * @projectName leet-code-record
 * @description: 10. 正则表达式匹配
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 *
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * @date 2023/4/6 15:54
 */
public class Demo {

    public static void main(String[] args) {
        /**
         * "mississippi"
         * "mis*is*p*."
         */
        System.out.println(isMatch2("mississippi","mis*is*p*."));
    }

    public static boolean isMatch2(String s, String p) {
        if(p.startsWith("*")){
            return false;
        }

        if(!p.startsWith(".") && !(s.charAt(0) == p.charAt(0))){
            return false;
        }


        if(!p.endsWith(".") && !(s.charAt(s.length()-1) == p.charAt(p.length()-1))){
            return false;
        }

        if(!p.contains("*")){
            if(s.length() != p.length()){
                return false;
            }

            for (int i = 0; i < p.length(); i++) {
                if(p.charAt(i) != '.' && p.charAt(i) != s.charAt(i)){
                    return false;
                }
            }
        }else{

            // TODO
            int index1 = 0;
            int index2 = p.indexOf("*")-1;
            for (int i = index1; i <index2 ; i++) {
                char c = p.charAt(i);
                if(c!='.' && c!= s.charAt(i)){
                    return false;
                }
            }




        }

        return true;
    }

    /**
     * 定义一个二维布尔数组match来表示s的前i个字符和p的前j个字符是否能够匹配。match[i][j]表示s的前i个字符能否被p的前j个字符匹配。
     * 初始化match[0][0]为true，表示空字符串和空规律可以匹配。
     * 初始化第一列match[i][0]为false（i>0），表示空规律无法匹配任何字符串。
     * 初始化第一行match[0][j]，只有当p的前j个字符都是'*'时，才能匹配空字符串，因此需要判断p字符串中连续的'*'是否占据了整个p的长度。
     * 当p[j-1]不是'*'时，若s[i-1]和p[j-1]匹配，则match[i][j] = match[i-1][j-1]，否则match[i][j] = false。
     * 当p[j-1]是'*'时，分两种情况：
     * 匹配0个：match[i][j] = match[i][j-2]
     * 匹配1个或多个：match[i][j] = match[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.') 解释：匹配0个时，直接跳过p的前j-2个字符；匹配1个或多个时，s的前i-1个字符和p的前j个字符已经匹配，此时只需判断s[i-1]和p[j-2]是否匹配即可。同时注意p[j-2]可能是'.'，所以需要用 || 操作符判断匹配。
     * 返回match[s.length()][p.length()]
     */

    public static boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] match = new boolean[m+1][n+1];
        match[0][0] = true;
        for(int j=1; j<=n; j++) {
            if(p.charAt(j-1) == '*') match[0][j] = match[0][j-2];
        }
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.') {
                    match[i][j] = match[i-1][j-1];
                } else if(p.charAt(j-1) == '*') {
                    match[i][j] = match[i][j-2]
                            || (match[i-1][j] && (s.charAt(i-1) == p.charAt(j-2)
                            || p.charAt(j-2) == '.'));
                }
            }
        }
        return match[m][n];
    }
}
